Power Efficient Range Assignment for Symmetric Connectivity in Static Ad Hoc Wireless Networks
Identifieur interne : 006212 ( Main/Exploration ); précédent : 006211; suivant : 006213Power Efficient Range Assignment for Symmetric Connectivity in Static Ad Hoc Wireless Networks
Auteurs : E. Althaus [Allemagne] ; G. C Linescu [États-Unis] ; I. I. M Ndoiu [États-Unis] ; S. Prasad [États-Unis] ; N. Tchervenski [États-Unis] ; A. Zelikovsky [États-Unis]Source :
- Wireless Networks [ 1022-0038 ] ; 2006-06-01.
English descriptors
Abstract
Abstract: In this paper we study the problem of assigning transmission ranges to the nodes of a static ad hoc wireless network so as to minimize the total power consumed under the constraint that enough power is provided to the nodes to ensure that the network is connected. We focus on the Min-Power Symmetric Connectivity problem, in which the bidirectional links established by the transmission ranges are required to form a connected graph. Implicit in previous work on transmission range assignment under asymmetric connectivity requirements is the proof that Min-Power Symmetric Connectivity is NP-hard and that the MST algorithm has a performance ratio of 2. In this paper we make the following contributions: (1) we show that the related Min-Power Symmetric Unicast problem can be solved efficiently by a shortest-path computation in an appropriately constructed auxiliary graph; (2) we give an exact branch and cut algorithm based on a new integer linear program formulation solving instances with up to 35–40 nodes in 1 hour; (3) we establish the similarity between Min-Power Symmetric Connectivity and the classic Steiner Tree problem in graphs, and use this similarity to give a polynomial-time approximation scheme with performance ratio approaching 5/3 as well as a more practical approximation algorithm with approximation factor 11/6; and (4) we give the results of a comprehensive experimental study comparing new and previously proposed heuristics with the above exact and approximation algorithms.
Url:
DOI: 10.1007/s11276-005-5275-x
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 002406
- to stream Istex, to step Curation: 002375
- to stream Istex, to step Checkpoint: 001526
- to stream Main, to step Merge: 006437
- to stream Main, to step Curation: 006212
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Power Efficient Range Assignment for Symmetric Connectivity in Static Ad Hoc Wireless Networks</title><author><name sortKey="Althaus, E" sort="Althaus, E" uniqKey="Althaus E" first="E." last="Althaus">E. Althaus</name></author><author><name sortKey="C Linescu, G" sort="C Linescu, G" uniqKey="C Linescu G" first="G." last="C Linescu">G. C Linescu</name></author><author><name sortKey="M Ndoiu, I I" sort="M Ndoiu, I I" uniqKey="M Ndoiu I" first="I. I." last="M Ndoiu">I. I. M Ndoiu</name></author><author><name sortKey="Prasad, S" sort="Prasad, S" uniqKey="Prasad S" first="S." last="Prasad">S. Prasad</name></author><author><name sortKey="Tchervenski, N" sort="Tchervenski, N" uniqKey="Tchervenski N" first="N." last="Tchervenski">N. Tchervenski</name></author><author><name sortKey="Zelikovsky, A" sort="Zelikovsky, A" uniqKey="Zelikovsky A" first="A." last="Zelikovsky">A. Zelikovsky</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:9A6A42775281B93B7C08ED2FF9EEADA6AA233A4E</idno><date when="2005" year="2005">2005</date><idno type="doi">10.1007/s11276-005-5275-x</idno><idno type="url">https://api.istex.fr/ark:/67375/VQC-KD70K7VQ-1/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">002406</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002406</idno><idno type="wicri:Area/Istex/Curation">002375</idno><idno type="wicri:Area/Istex/Checkpoint">001526</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001526</idno><idno type="wicri:doubleKey">1022-0038:2005:Althaus E:power:efficient:range</idno><idno type="wicri:Area/Main/Merge">006437</idno><idno type="wicri:Area/Main/Curation">006212</idno><idno type="wicri:Area/Main/Exploration">006212</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Power Efficient Range Assignment for Symmetric Connectivity in Static Ad Hoc Wireless Networks</title><author><name sortKey="Althaus, E" sort="Althaus, E" uniqKey="Althaus E" first="E." last="Althaus">E. Althaus</name><affiliation wicri:level="3"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, D-66123, Saarbrücken</wicri:regionArea><placeName><region type="land" nuts="2">Sarre (Land)</region><settlement type="city">Sarrebruck</settlement></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country></affiliation></author><author><name sortKey="C Linescu, G" sort="C Linescu, G" uniqKey="C Linescu G" first="G." last="C Linescu">G. C Linescu</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><placeName><region type="state">Illinois</region></placeName><wicri:cityArea>Department of Computer Science, Illinois Institute of Technology, 60616, Chicago</wicri:cityArea></affiliation><affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country></affiliation></author><author><name sortKey="M Ndoiu, I I" sort="M Ndoiu, I I" uniqKey="M Ndoiu I" first="I. I." last="M Ndoiu">I. I. M Ndoiu</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><placeName><region type="state">Connecticut</region></placeName><wicri:cityArea>Computer Science and Engineering Department, University of Connecticut, 371 Fairfield Rd., Unit 2155, 06269, Storrs</wicri:cityArea></affiliation><affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country></affiliation></author><author><name sortKey="Prasad, S" sort="Prasad, S" uniqKey="Prasad S" first="S." last="Prasad">S. Prasad</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><placeName><region type="state">Géorgie (États-Unis)</region></placeName><wicri:cityArea>Department of Computer Science, Georgia State University, 30303, Atlanta</wicri:cityArea></affiliation><affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country></affiliation></author><author><name sortKey="Tchervenski, N" sort="Tchervenski, N" uniqKey="Tchervenski N" first="N." last="Tchervenski">N. Tchervenski</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><placeName><region type="state">Illinois</region></placeName><wicri:cityArea>Department of Computer Science, Illinois Institute of Technology, 60616, Chicago</wicri:cityArea></affiliation><affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country></affiliation></author><author><name sortKey="Zelikovsky, A" sort="Zelikovsky, A" uniqKey="Zelikovsky A" first="A." last="Zelikovsky">A. Zelikovsky</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><placeName><region type="state">Géorgie (États-Unis)</region></placeName><wicri:cityArea>Department of Computer Science, Georgia State University, 30303, Atlanta</wicri:cityArea></affiliation><affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country></affiliation></author></analytic><monogr></monogr><series><title level="j">Wireless Networks</title><title level="j" type="sub">The Journal of Mobile Communication, Computation and Information</title><title level="j" type="abbrev">Wireless Netw</title><idno type="ISSN">1022-0038</idno><idno type="eISSN">1572-8196</idno><imprint><publisher>Kluwer Academic Publishers</publisher><pubPlace>Boston</pubPlace><date type="published" when="2006-06-01">2006-06-01</date><biblScope unit="volume">12</biblScope><biblScope unit="issue">3</biblScope><biblScope unit="page" from="287">287</biblScope><biblScope unit="page" to="299">299</biblScope></imprint><idno type="ISSN">1022-0038</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">1022-0038</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>ad hoc wireless networks</term><term>algorithms</term><term>power range assignment</term><term>symmetric connectivity</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: In this paper we study the problem of assigning transmission ranges to the nodes of a static ad hoc wireless network so as to minimize the total power consumed under the constraint that enough power is provided to the nodes to ensure that the network is connected. We focus on the Min-Power Symmetric Connectivity problem, in which the bidirectional links established by the transmission ranges are required to form a connected graph. Implicit in previous work on transmission range assignment under asymmetric connectivity requirements is the proof that Min-Power Symmetric Connectivity is NP-hard and that the MST algorithm has a performance ratio of 2. In this paper we make the following contributions: (1) we show that the related Min-Power Symmetric Unicast problem can be solved efficiently by a shortest-path computation in an appropriately constructed auxiliary graph; (2) we give an exact branch and cut algorithm based on a new integer linear program formulation solving instances with up to 35–40 nodes in 1 hour; (3) we establish the similarity between Min-Power Symmetric Connectivity and the classic Steiner Tree problem in graphs, and use this similarity to give a polynomial-time approximation scheme with performance ratio approaching 5/3 as well as a more practical approximation algorithm with approximation factor 11/6; and (4) we give the results of a comprehensive experimental study comparing new and previously proposed heuristics with the above exact and approximation algorithms.</div></front></TEI><affiliations><list><country><li>Allemagne</li><li>États-Unis</li></country><region><li>Connecticut</li><li>Géorgie (États-Unis)</li><li>Illinois</li><li>Sarre (Land)</li></region><settlement><li>Sarrebruck</li></settlement></list><tree><country name="Allemagne"><region name="Sarre (Land)"><name sortKey="Althaus, E" sort="Althaus, E" uniqKey="Althaus E" first="E." last="Althaus">E. Althaus</name></region><name sortKey="Althaus, E" sort="Althaus, E" uniqKey="Althaus E" first="E." last="Althaus">E. Althaus</name></country><country name="États-Unis"><region name="Illinois"><name sortKey="C Linescu, G" sort="C Linescu, G" uniqKey="C Linescu G" first="G." last="C Linescu">G. C Linescu</name></region><name sortKey="C Linescu, G" sort="C Linescu, G" uniqKey="C Linescu G" first="G." last="C Linescu">G. C Linescu</name><name sortKey="M Ndoiu, I I" sort="M Ndoiu, I I" uniqKey="M Ndoiu I" first="I. I." last="M Ndoiu">I. I. M Ndoiu</name><name sortKey="M Ndoiu, I I" sort="M Ndoiu, I I" uniqKey="M Ndoiu I" first="I. I." last="M Ndoiu">I. I. M Ndoiu</name><name sortKey="Prasad, S" sort="Prasad, S" uniqKey="Prasad S" first="S." last="Prasad">S. Prasad</name><name sortKey="Prasad, S" sort="Prasad, S" uniqKey="Prasad S" first="S." last="Prasad">S. Prasad</name><name sortKey="Tchervenski, N" sort="Tchervenski, N" uniqKey="Tchervenski N" first="N." last="Tchervenski">N. Tchervenski</name><name sortKey="Tchervenski, N" sort="Tchervenski, N" uniqKey="Tchervenski N" first="N." last="Tchervenski">N. Tchervenski</name><name sortKey="Zelikovsky, A" sort="Zelikovsky, A" uniqKey="Zelikovsky A" first="A." last="Zelikovsky">A. Zelikovsky</name><name sortKey="Zelikovsky, A" sort="Zelikovsky, A" uniqKey="Zelikovsky A" first="A." last="Zelikovsky">A. Zelikovsky</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006212 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006212 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:9A6A42775281B93B7C08ED2FF9EEADA6AA233A4E
|texte= Power Efficient Range Assignment for Symmetric Connectivity in Static Ad Hoc Wireless Networks
}}
| This area was generated with Dilib version V0.6.33. |  |